package bintree;

import java.util.Deque;
import java.util.LinkedList;

/**
 *  二叉树的基本操作实现
 */

//二叉树的节点
class TreeNode<E> {
    //当前节点的值
    E val;
    //左子树的跟
    TreeNode<E> left;
    //右子树的跟
    TreeNode<E> right;
    //构造方法
    public TreeNode(E val) {
        this.val = val;
    }
}


public class MyBinTree<E> {
    public TreeNode<Character> root;//根节点

    //建立一个测试二叉树
    public void build(){
        //假设有8个节点
        TreeNode<Character> node1 = new TreeNode<>('A');
        TreeNode<Character> node2 = new TreeNode<>('B');
        TreeNode<Character> node3 = new TreeNode<>('C');
        TreeNode<Character> node4 = new TreeNode<>('D');
        TreeNode<Character> node5 = new TreeNode<>('E');
        TreeNode<Character> node6 = new TreeNode<>('F');
        TreeNode<Character> node7 = new TreeNode<>('G');
        TreeNode<Character> node8 = new TreeNode<>('H');
        //节点的连接

        //A
        node1.left = node2;
        node1.right = node3;
        //B
        node2.left = node4;
        node2.right = node5;
        //E
        node5.left = node7;
        //G
        node7.right = node8;
        //C
        node3.right = node6;

        //连接根节点
        root = node1;
    }

    /**
     * 传入一颗二叉树的根节点root。就能按照前序遍历根左右的方式进行输出
     */
    public void preOrder(TreeNode root){
        //终止条件
        if(root == null){
            return;
        }
        //我们只负责打印跟
        System.out.print(root.val + " ");
        //左子树的输出交给子函数
        preOrder(root.left);
        //右子树的输出交给子函数
        preOrder(root.right);
    }

    /**
     * 传入一颗二叉树的根节点root。就能按照中序遍历左根右的方式进行输出
     */
    public void inOrder(TreeNode root){
        //终止条件
        if(root == null){
            return;
        }
        //左子树的输出交给子函数
        inOrder(root.left);

        //我们只负责打印跟
        System.out.print(root.val + " ");

        //右子树的输出交给子函数
        inOrder(root.right);

    }

    /**
     * 传入一颗二叉树的根节点root。就能按照后序遍历左右根的方式进行输出
     * @param root
     */
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先打印左子树,交给子函数
        postOrder(root.left);
        // 再打印右子树
        postOrder(root.right);
        // 最后打印根
        System.out.print(root.val + " ");
    }

    /**
     * 传入一颗以root为根的二叉树，就能求出节点个数为多少
     */
    public int getNodes(TreeNode root){
        //1.边界
        if(root == null){
            return 0;
        }
        //此时二叉树不为空，root ！= null，根节点存在，所以至少存在 1
        //总节点个数 = 根节点 + 左子树的所用节点 + 右子树的所有节点
        return 1 + getNodes(root.left) + getNodes(root.right);

    }

    /**
     * 使用层序遍历统计二叉树的节点个数
     */
    public int getNodesNonRecursion(TreeNode root){
        //1.边界
        if(root == null){
            return 0;
        }
        int size = 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            //此处的遍历指的是讲节点个数统计
            size ++;
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }

        return size;
    }


    /**
     * 传入一颗以root为根的树，就能求出叶子节点的个数
     */
    public int getLeafNodes(TreeNode root){
        //1. 边界
        if(root == null){
            return 0;//此时节点都为空了，哪来什么子树
        }
        //到了这里说明该节点不为空，看看它的子树
        //2.判断是否为叶子节点
        if(root.left == null && root.right == null){
            return 1;
        }
        //3.到了这里说明该节点不是叶子节点，且有子树。
        //看看它的子树里面是否存在叶子节点。
        //总叶子节点个数 = 左树中的叶子节点个数 + 右树中的叶子节点个数
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }

    /**
     * 传入一颗以root为根的二叉树，就能求出第k层的节点个数 k <= height(root)
     */
    public int getKLevelNodes(TreeNode root,int k){
        //1.边界
        if(root == null || k <= 0){
            return 0;
        }
        //当k == 1时，说明求的是输出的根节点这层
        if(k == 1){
            //第一层为根节点，肯定只有一个。
            return 1;
        }
        //当k ！= 1时，说明改层不是要求的层次，交给子方法去求
        // 求以root为根的第k层结点个数 =
        // 以root.left为根的第k - 1层结点个数 + 以root.right为根的第k - 1层结点个数
        return getKLevelNodes(root.left, k - 1) + getKLevelNodes(root.right, k - 1);
    }

    /**
     * 传入一颗以root为根的二叉树，就能求出该树的高度是多少
     */
    public int height(TreeNode root){
        //1.边界
        if(root == null){
            return 0;
        }
//        //2.该节点下面没有子树了，这就是它的最高高度了。
//        if(root.left == null && root.right == null){
//            return 1;
//        }
//        int left = height(root.left);//左子树里面最深的高度
//        int right = height(root.right);//右子树里面最深的高度
//        return 1 + (left > right ? left : right);

        //也可以这么写：
        // 1就是当前树根所在的第一层
        // 树高 = 根节点这一层 + max(左子树的树高，右子树的树高)
        return 1 + Math.max(height(root.left), height(root.right));
    }

    /**
     *  判断以root为根的二叉树中是否包含指定值val
     */
    public boolean contains(TreeNode<E> root,E val){
        if (root == null) {
            return false;
        }
        if (root.val.equals(val)) {
            return true;
        }
        // 继续在左子树和右子树中寻找是否包含指定值
        return contains(root.left,val) || contains(root.right,val);
    }

    /**
     * 借住队列，实现二叉树的层序遍历
     */
    public void levelOrder(TreeNode<E> root){
        //创建一个队列,用双端队列
        Deque<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(root);
        //循环的终止条件就是队列为空
        while(!queue.isEmpty()){
            //当前队列里面的节点个数，就是当前需要执行的循环次数。
            int n = queue.size();
            for (int i = 0; i < n; i++) {

                TreeNode<E> node = queue.poll();//出队列
                System.out.print(node.val + " ");//打印弹出的节点

                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }

            }

        }

    }

}
